An important first step when deploying a wireless ad hoc network is neighbordiscovery in which every node attempts to determine the set of nodes it cancommunicate with in one wireless hop. In the recent years, cognitive radio (CR)technology has gained attention as an attractive approach to alleviate spectrumcongestion. A cognitive radio transceiver can operate over a wide range offrequencies, possibly scanning multiple frequency bands. A cognitive radio nodecan opportunistically utilize unused wireless spectrum without interferencefrom other wireless devices in its vicinity. Due to spatial variations infrequency usage and hardware variations in radio transceivers, different nodesin the network may perceive different subsets of frequencies available to themfor communication. This heterogeneity in the available channel sets across thenetwork increases the complexity of solving the neighbor discovery problem in acognitive radio network. In this work, we design and analyze several randomizedalgorithms for neighbor discovery in such a (heterogeneous) network under avariety of assumptions (e.g. maximum node degree known or unknown) for bothsynchronous and asynchronous systems under minimal knowledge. We also show thatour randomized algorithms are naturally suited to tolerate unreliable channelsand adversarial attacks.
展开▼
